import java.util.Arrays;

/**
 * 209. 长度最小的子数组
 * https://leetcode.cn/problems/minimum-size-subarray-sum
 */
class MinimumSizeSubarraySum {
/**
 * 方法： minSubArrayLen
 * 逻辑: 使用滑动窗口技术，找到和大于等于目标值的最小长度子数组。
 * Args:
 *   target: 目标和
 *   nums: 整数数组
 * Returns:
 *   满足条件的最小子数组长度，如果没有找到则返回0
 * Time:  
 *   O(n) - 每个元素最多被访问两次（一次通过right指针，一次通过left指针）
 * Space:  
 *   O(1) - 只使用了常数个额外变量
 */
public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int ans = n + 1;
    int sum = 0; //子数组元素和
    int left = 0; // 子数组左端点
    for(int right = 0; right < n; right++){
        sum += nums[right];
        while (sum >= target){
            ans = Math.min(ans, right - left + 1);
            sum -= nums[left];
            left ++;
        }
    }
    return ans <= n? ans : 0;
}

/**
 * 方法： minSubArrayLen1
 * 逻辑: 使用前缀和数组和二分查找，找到和大于等于目标值的最小长度子数组。
 * Args:
 *   s: 目标和
 *   nums: 整数数组
 * Returns:
 *   满足条件的最小子数组长度，如果没有找到则返回0
 * Time:  
 *   O(nlogn) - 计算前缀和数组需要O(n)，每次二分查找需要O(logn)，共进行n次二分查找
 * Space:  
 *   O(n) - 使用了前缀和数组
 */
public int minSubArrayLen1(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int ans = n + 1; //或者Integer.MAX_VALUE
    int[] sums = new int[n + 1];
    // 为了方便计算，令 size = n + 1
    // sums[0] = 0 意味着前 0 个元素的前缀和为 0
    // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
    // 以此类推
    for (int i = 1; i <= n; i++) {
        sums[i] = sums[i - 1] + nums[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        int target = s + sums[i - 1];
        int bound = Arrays.binarySearch(sums, target);
        if (bound < 0) {
            bound = -bound - 1;
        }
        if (bound <= n) {
            ans = Math.min(ans, bound - (i - 1));
        }
    }
    return ans >= (n + 1) ? 0 : ans;
}
}